Garbage collection is a technique used to manage in an automated fashion memory blocks that have been allocated for use by programs using objects associated with a runtime system, without requiring that the programs themselves or other application code with which such memory blocks are associated keep track of and when finished de-allocate said memory blocks. One use for such memory is as the contents of an “Object”. Blocks that are roots (e.g., stack local variables and global variables and those registered as being held externally) and/or that are reachable from a root block via a chain of one or more explicit or “strong” references are kept alive, while blocks that are no longer reachable, indicating they are no longer in use (i.e., referenced by) by any live object, are “garbage collected”, that is, de-allocated and returned to the runtime system, thus making available for other use the memory allocated previously to such objects. Providing a “garbage collected” runtime system simplifies the task of application developers and avoids problems, such as “memory leaks”, crashes due to stale references to prematurely de-allocated blocks, and other related failures, that can occur if memory resources allocated to application objects are not released when and only when such objects are no longer in use.
In at least some distributed environments, such as network environments or where multiple runtime systems share a memory address space within a single computer system, it is possible for an object in one system to have external references to objects in other runtime and/or physical systems. Such external references are considered to be part of the “root” set, such that objects to which such external references are made and any object reachable from such an externally referenced object, are kept alive. FIG. 1A illustrates an example of an environment in which multiple runtime systems are present within an address space. The address space 102 may include, for example, an address space within a computer system's memory. A corresponding memory “heap” comprising a portion of address space 102 has been assigned to the sole use of runtime systems 104, 106, 108, and 110, respectively. Examples of such runtime systems include JavaScript, Java, and Objective C runtime systems, and runtime systems associated with other scripting and/or programming languages, such as Python, Ruby, Perl, and Smalltalk. Typically, each such runtime environment would have its own garbage collector responsible for identifying and reclaiming memory associated with unused objects.
FIG. 1B illustrates examples of external references to objects in other runtime systems. In the example shown, an object 140 in runtime system 104 has an external reference to an object 142 in runtime system 106, the external reference being represented in FIG. 1B by the black arrow running between objects 140 and 142. Similarly, object 142 in runtime system 106 has an external reference to object 146 in runtime system 110, which in turn has an external reference to object 144 in runtime system 108, which in turn has an external reference to object 140 in runtime system 104, thereby completing a loop of external references among the objects 140-144.
In the typical prior art approach, a garbage collector is configured to keep alive a local object that is not reachable locally but to which an external reference is present, and to only garbage collect such an object once the external reference has been removed and/or it is determined that the referring object is no longer present. FIG. 2 illustrates an example of how a typical prior art garbage collector handles external references. If an object is not reachable locally (202), it is kept alive (208) if an external reference to the object exists (204); otherwise, i.e., if there is no external reference to the object, it is garbage collected (i.e., associated memory de-allocated) (206). However, the typical approach can result in objects that make references to one another, such as in the example shown in FIG. 1B, from being garbage collected. Each is kept alive by the local garbage collector of its local runtime environment due to the presence of an external reference from at least one external object that is still present in that external object's own runtime system, which results in the objects keeping each other alive, each in its respective runtime system, even though none of the objects are needed or in use.
Therefore, there is a need for a way to manage memory more effectively in a multiple runtime system environment.